11552. Arrangement

 

There are m students in a class, n of whom are girls. The teacher, Mr. X, wants to arrange all the students in a single row. He believes that the girls in his class are too talkative, so he does not want any two girls to stand next to each other.

Mr. X wants to know in how many different ways he can arrange all  students in a row while satisfying this condition. Help him find the answer.

 

Input. The first line contains the number of test cases t (1 ≤ t ≤ 105).  Each of the following t lines contains two integers m and n (1 < n ≤ m ≤ 106).

 

Output. For each test case, print one integer – the number of valid arrangements modulo 109 + 7.

 

Sample input

Sample output

2

3 2

4 2

2

12

 

 

SOLUTION

combinatorics

 

Algorithm analysis

The number of boys in the class is b = m – n. Since all boys are distinguishable, the number of ways to arrange them is

b! = (m – n)!

Around the b boys, there are b + 1 positions where girls can be placed:

There are n girls in total. Therefore, we need to choose n distinct positions out of the b + 1 available positions in which to place the girls:

If n > b + 1, then the answer is 0.

The girls are also distinguishable, so they can be permuted.

Thus, the total number of ways to arrange all the students in a row is equal to

 

Example

Consider the test case m = 3, n = 2.

The number of boys is b = m – n = 3 – 2 = 1. The answer is equal to

 = 1 * 1 * 2 = 2

Consider the test case m = 4, n = 2.

The number of boys is b = m – n = 4 – 2 = 2. The answer is equal to

 = 3 * 2 * 2 = 12

 

Algorithm implementation

Let us define the arrays:

·        fact, which stores the factorials of numbers modulo MOD,

·        factinv, which stores the modular inverses of these factorials modulo MOD:

fact[n] = n! mod 1000000007

factinv[n] = n! -1 mod 1000000007

 

#define MAX 1000001

#define MOD 1000000007

ll fact[MAX], factinv[MAX];

 

The function pow computes the power of a number modulo a given modulus:

xn mod p

 

ll pow(ll x, ll n, ll p)

{

  if (n == 0) return 1;

  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);

  return (x * pow(x, n - 1, p)) % p;

}

 

The inverse function finds the number that is the modular inverse of x with respect to a prime modulo p. Since p is a prime number, by Fermat’s Little Theorem the following holds:

xp-1 mod p = 1 for any 1 ≤ x < p

This can be rewritten as (x * xp-2) mod p = 1, from which it follows that the modular inverse of x is xp-2 mod p.

 

ll inverse(ll x, ll p)

{

  return pow(x, p - 2, p);

}

 

The Cnk function computes the binomial coefficient using the formula:

 =

 

ll Cnk(int n, int k)

{

  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;

}

 

The main part of the program. Fill the arrays of factorials fact and inverse factorials factinv.

 

fact[0] = 1;

for (i = 1; i < MAX; i++)

  fact[i] = (fact[i - 1] * i) % MOD;

 

factinv[0] = 1;

for (i = 1; i < MAX; i++)

  factinv[i] = inverse(fact[i], MOD);

 

Read the number of test cases tests.

 

scanf("%d", &tests);

while (tests--)

{

 

Read the data for the current test case.

 

  scanf("%d %d", &m, &n);

 

Compute the number of boys b = m – n.

 

  b = m - n;

 

Compute and print the answer using the formula:

 

  res = ((fact[n] * fact[b]) % MOD * Cnk(b + 1, n)) % MOD;

  printf("%lld\n", res);

}